|
In automata theory, the thread automaton (plural: automata) is an extended type of finite-state automata that recogne a mildly context-sensitive language class above the tree-adjoining languages.〔 〕 ==Formal definition== A thread automaton consists of * a set ''N'' of states,〔called ''non-terminal symbols'' by Villemonte (2002), p.1r〕 * a set Σ of terminal symbols, * a start state ''A''''S'' ∈ ''N'', * a final state ''A''''F'' ∈ ''N'', * a set ''U'' of path components, * a partial function δ: ''N'' → ''U''⊥, where ''U''⊥ = ''U'' ∪ for ⊥ ∉ ''U'', * a finite set Θ of transitions. A path ''u''1...''u''''n'' ∈ ''U'' * is a string of path components ''u''''i'' ∈ ''U''; ''n'' may be 0, with the empty path denoted by ε. A thread has the form ''u''1...''u''''n'':''A'', where ''u''1...''u''''n'' ∈ ''U'' * is a path, and ''A'' ∈ ''N'' is a state. A thread store ''S'' is a finite set of threads, viewed as a partial function from ''U'' * to ''N'', such that ''dom''(''S'') is closed by prefix. A thread automaton configuration is a triple ‹''l'',''p'',''S''›, where ''l'' denotes the current position in the input string, ''p'' is the active thread, and ''S'' is a thread store containing ''p''. The initial configuration is ‹0,ε,›. The final configuration is ‹''n'',''u'',›, where ''n'' is the length of the input string and ''u'' abbreviates δ(''A''''S''). A transition in the set Θ may have one of the following forms, and changes the current automaton configuration in the following way: * SWAP ''B'' →''a'' ''C'': consumes the input symbol ''a'', and changes the state of the active thread: : changes the configuration from ‹''l'',''p'',''S''∪› to ‹''l''+1,''p'',''S''∪› * SWAP ''B'' →ε ''C'': similar, but consumes no input: : changes ‹''l'',''p'',''S''∪› to ‹''l'',''p'',''S''∪› * PUSH ''C'': creates a new subthread, and suspends its parent thread: : changes ‹''l'',''p'',''S''∪› to ‹''l'',''pu'',''S''∪› where ''u''=δ(''B'') and ''pu''∉dom(''S'') * POP ()''C'': ends the active thread, returning control to its parent: : changes ‹''l'',''pu'',''S''∪› to ‹''l'',''p'',''S''∪› where δ(''C'')=⊥ and ''pu''∉dom(''S'') * SPUSH () ''D'': resumes a suspended subthread of the active thread: : changes ‹''l'',''p'',''S''∪› to ‹''l'',''pu'',''S''∪› where ''u''=δ(''B'') * SPOP () ''D'': resumes the parent of the active thread: : changes ‹''l'',''pu'',''S''∪› to ‹''l'',''p'',''S''∪› where δ(''C'')=⊥ One may prove that δ(''B'')=''u'' for POP and SPOP transitions, and δ(''C'')=⊥ for SPUSH transitions.〔Villemonte (2002), p.1r-2r〕 An input string is accepted by the automaton if there is a sequence of transitions changing the initial into the final configuration. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Thread automaton」の詳細全文を読む スポンサード リンク
|